๐Ÿ“‚ ๋ฐฐ์—ด (Array)

@Seongukbaek Posted May 18, 2022 ยท Updated May 18, 2022 ยท 5 min read

๐Ÿงท ๋ฐฐ์—ด (Array)

๋™์ผํ•œ ์ž๋ฃŒํ˜•์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์—ฐ์†๋œ ๊ณต๊ฐ„์— ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์—ฐ๊ด€๋œ ๋ฐ์ดํ„ฐ๋ฅผ ๊ทธ๋ฃนํ™”ํ•˜์—ฌ ๋ฌถ์–ด์ค€๋‹ค.

๐Ÿชš ์žฅ์ 

  • ์—ฐ๊ด€๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ธฐ ์œ„ํ•œ ๋ณ€์ˆ˜์˜ ์„ ์–ธ์„ ์ค„์—ฌ์ค€๋‹ค.
  • ๋ฐ˜๋ณต๋ฌธ ๋“ฑ์„ ์ด์šฉํ•˜์—ฌ ๊ณ„์‚ฐ ๊ณผ์ •์„ ์‰ฝ๊ฒŒ ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋‹ค.
int[] array = { 1,2,3,4,5,6 }; int arraySize = array.length;

๐Ÿชš ๋ฐฐ์—ด ํšŒ์ „ ํ”„๋กœ๊ทธ๋žจ

๊ธฐ๋ณธ์ ์ธ ํšŒ์ „ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • tmp ์— ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค์˜ ๊ฐ’์„ ์ €์žฅํ•˜๊ณ , ๋‚˜๋จธ์ง€ ๊ฐ’๋“ค์„ ํ•œ ์นธ์”ฉ ์•ž์œผ๋กœ ๋•ก๊ฒจ์„œ ์ €์žฅํ•œ๋‹ค.
  • ์ดํ›„ array[n] ์— tmp ๊ฐ’์„ ์ €์žฅํ•œ๋‹ค.

์ €๊ธ€๋ง ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ gcd๋ฅผ ์ด์šฉํ•ด ์ง‘ํ•ฉ์„ ๋‚˜๋ˆ„์–ด ์—ฌ๋Ÿฌ ์š”์†Œ๋ฅผ ํ•œ๊บผ๋ฒˆ์— ์ด๋™์‹œํ‚จ๋‹ค.
  • ์ฃผ์–ด์ง„ ๋ฐฐ์—ด์ด int[] array = {1,2,3,4,5,6,7,8,9,10,11,12} ๋ผ๋ฉด, 1,2,3 ์„ ๋’ค๋กœ ์˜ฎ๊ธธ ๋•Œ, ์ธ๋ฑ์Šค๋ฅผ 3๊ฐœ์”ฉ ๋ฌถ๊ณ  ํšŒ์ „์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
  • []arrary -> {4,2,3,7,5,6,10,8,9,1,11,12}
  • []arrary -> {4,5,3,7,8,6,10,11,9,1,2,12}
  • []arrary -> {4,5,6,7,8,9,10,11,12,1,2,3}

์—ญ์ „ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ํšŒ์ „์‹œํ‚ค๋Š” ์ˆ˜์— ๋Œ€ํ•ด ๊ตฌ๊ฐ„์„ ๋‚˜๋ˆ  reverse๋กœ ๊ตฌํ˜„ํ•œ๋‹ค.

d=2 ์ด๋ฉด, ๊ตฌ๊ฐ„์„ 1,2 / 3,4,5,6,7 ๋กœ ๋‚˜๋ˆˆ๋‹ค.

  • ์ฒซ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ reverse -> 2,1
  • ๋‘ ๋ฒˆ์งธ ๊ตฌ๊ฐ„ reverse - > 7,6,5,4,3
  • ํ•ฉ์น˜๊ธฐ -> 2,1,7,6,5,4,3
  • ํ•ฉ์นœ ๋ฐฐ์—ด์„ reverse -> 3,4,5,6,7,1,2
void reverseArr(int[] array, int start, int end) { while (start < end) { int temp = array[start]; array[start] = array[end]; array[end] = temp; start++; end--; } } void rotateLeft(int[] array, int d, int n) { reverseArr(array, 0, d - 1); reverseArr(array, d, n - 1); reverseArr(array, 0, n - 1); }

๐Ÿชš ๋ฐฐ์—ด์˜ ํŠน์ • ์ตœ๋Œ€ ํ•ฉ ๊ตฌํ•˜๊ธฐ

array[i] ๊ฐ€ ์žˆ์„ ๋•Œ, i * array[i] ์˜ ํ•ฉ์ด ๊ฐ€์žฅ ํด ๋•Œ ๊ทธ ๊ฐ’์„ ์ถœ๋ ฅํ•˜๊ธฐ

  • ์ด๋ฅผ ํšŒ์ „์„ ํ†ตํ•ด ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.
// Input array = { 1, 20, 2, 10 } // Output 72 2๋ฒˆ ํšŒ์ „ํ–ˆ์„ ๋•Œ ์•„๋ž˜์™€ ๊ฐ™์ด ์ตœ๋Œ“๊ฐ’์ด ๋‚˜์˜จ๋‹ค. { 2, 10, 1, 20 } 20 * 3 + 1 * 2 + 10 * 1 + 20 * 0 = 72

์ ‘๊ทผ๋ฒ•

  • array[i] ์˜ ์ „์ฒด ํ•ฉ๊ณผ i * array[i] ์˜ ์ „์ฒด ํ•ฉ์„ ์ €์žฅํ•  ๋ณ€์ˆ˜ ์„ ์–ธ
  • ์ตœ์ข… ๊ฐ€์žฅ ํฐ sum ๊ฐ’์„ ์ €์žฅํ•  ๋ณ€์ˆ˜ ์„ ์–ธ
  • ๋ฐฐ์—ด์„ ํšŒ์ „์‹œํ‚ค๋ฉด์„œ i * array[i] ์˜ ํ•ฉ ์ค‘ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•œ๋‹ค.

ํ•ด๊ฒฐ๋ฒ•

  • ํšŒ์ „ ์—†์ด i * array[i] ์˜ sum์„ ์ €์žฅํ•œ ๊ฐ’ = R0
  • 1๋ฒˆ ํšŒ์ „ํ•˜๊ณ  i * array[i] ์˜ sum์„ ์ €์žฅํ•œ ๊ฐ’ = R1
  • ์ด ๋‘ ๊ฐœ๋ฅผ ๋นผ๋ฉด R1 - R0 = array[0] + array[1] + ... array[n - 2] - (n - 1) * array[n - 1]
  • ์ด๋ฅผ ๊ณ„์† ๋ฐ˜๋ณตํ•˜๋‹ค๋ณด๋ฉด, Rj - R(j-1) = arrSum - n * array[n - j] ๋ผ๋Š” ๊ทœ์น™์„ ์–ป์„ ์ˆ˜ ์žˆ๋‹ค.
int arrSum = ๋ฐฐ์—ด์˜ ์ด ํ•ฉ int maxSum = ํšŒ์ „์—†์ด ๊ตฌํ•œ i * array[i]์˜ sum; for (int j = 1; j < n; j++){ curSum = curSum + arrSum - n*arr[n-j]; if ( curSum > maxSum ) maxSum = curSum; } return maxSum;

๐Ÿชš ํŠน์ • ๋ฐฐ์—ด์„ array[i] = i ๋กœ ์žฌ๋ฐฐ์—ด

์ฃผ์–ด์ง„ ๋ฐฐ์—ด์—์„œ array[i] = i ๊ฐ€ ๊ฐ€๋Šฅํ•œ ๊ฒƒ๋งŒ ์žฌ๋ฐฐ์—ด์‹œํ‚ค๊ธฐ (array[i] = i ๊ฐ€ ์—†์œผ๋ฉด -1๋กœ ์ฑ„์šด๋‹ค.)

// Input array = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 } // Output { -1, 1, 2, 3, 4, -1, 6, -1, -1, 9 }

์ ‘๊ทผ๋ฒ•

  • array[i] != -1 && array[i] != i ๊ฐ€ ์šฐ์„  ์กฐ๊ฑด
  • ํ•ด๋‹น ๊ฐ’์„ ์ €์žฅ(x)ํ•ด๋‘๊ณ , ์ด ๊ฐ’์ด x ์ผ๋•Œ array[x] ๋ฅผ ํƒ์ƒ‰
  • array[x] ๊ฐ’์„ ์ €์žฅ(y)ํ•ด๋‘๊ณ , array[x] ๊ฐ€ -1์ด ์•„๋‹ˆ๋ฉด์„œ array[x] ๊ฐ€ x ๊ฐ€ ์•„๋‹Œ ๋™์•ˆ์„ ํƒ์ƒ‰
  • array[x] ๋ฅผ x ๊ฐ’์œผ๋กœ ์ €์žฅํ•ด์ฃผ๊ณ , ๊ธฐ์กด์˜ x ๋ฅผ y ๋กœ ์ˆ˜์ •
int fix(int[] array, int len) { for (int i = 0; i < len; i++) { if (array[i] != -1 && array[i] != i) { int x = array[i]; while (array[x] != -1 && array[x] != x) { int y = array[x]; array[x] = x; x = y; } array[x] = x; if (array[i] != i) array[i] = -1; } } }

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€